\bigskip
\bigskip
{\magonebf 5.11 Node priority queues (node\_pq)}

\decl node\_pq I 

{\bf 1. Definition}

An instance $Q$ of the parameterized data type \name\ is a partial 
function from the nodes of a graph $G$ to the linearly ordered type $I$.

\bigskip
{\bf 2. Creation}

\create Q (G)

creates an instance $Q$ ot type \name\ for the nodes of graph $G$
with $dom(Q)=\emptyset$.



\bigskip
{\bf 3. Operations} 

\medskip
\+\op void insert {node\ v,\ I\ i}    
                        {adds the node $v$ with information $i$ to}
\+\nop                  {\var. \precond $v\not\in dom(Q)$.}
\smallskip
\+\op I    inf {node\ v}
                        {returns information of node $v$.}
\smallskip
\+\op bool member {node\ v}
                        {returns true if $v$ in \var, false otherwise.}
\smallskip
\+\op void decrease\_inf {node\ v,\ I\ i} 
                        {makes $i$ the new information of node $v$}
\+\nop                  {(\precond $i \le Q(v)$).}
\smallskip
\+\op node find\_min {}          
                        {returns a node with the minimal }
\+\nop                  {information(nil if \var\ is empty)}
\smallskip
\+\op void del {node\ v}           
                        {removes the node $v$ from \var }
\smallskip
\+\op node del\_min {}             
                        {removes a node with the minimal}
\+\nop                  {information from \var\ and returns it}
\+\nop                  {(nil if \var\ is empty)}
\smallskip
\+\op int      size  {}
                        {returns $|dom(Q)|$. }
\smallskip
\+\op void clear {}                 
                        {makes $Q$ the empty node priority queue.}
\smallskip

\+\op bool  empty {}                 
                        {returns true if \var\ is the empty node}
\+\nop                  {priority queue, false otherwise.}


\bigskip
{\bf 4. Implementation}

Node priority queues are implemented by fibonacci heaps and node arrays.
Operations insert, del\_node, del\_min take time $O(\log n)$, find\_min, 
decrease\_inf, empty take time $O(1)$ and clear takes time $O(m)$, where 
$m$ is the size of $Q$. The space requirement is $O(n)$, where $n$ is the 
number of nodes of $G$.

\vfill\eject

